package com.wss.lsl.test.driven.arithmetic.sort;

/**
 * 排序工具
 * 
 * @author Administrator
 * 
 */
public class SortUtils {

	/**
	 * 快速排序算法
	 * 
	 * @param data
	 * @param low
	 * @param up
	 */
	public static void quicklySort(int[] data, int low, int up) {
		if (low >= up) {
			return;
		}
		int t = data[low], i = low, j = up + 1;
		while (true) {
			do {
				i++;
			} while (i <= up && data[i] < t);
			do {
				j--;
			} while (data[j] > t);
			if (i > j) {
				break;
			}
			// i,j 数据交换位置
			int temp = data[i];
			data[i] = data[j];
			data[j] = temp;
		}
		// low,j 交换位置
		data[low] = data[j];
		data[j] = t;
		quicklySort(data, low, j - 1);
		quicklySort(data, j + 1, up);
	}

	/**
	 * 快排
	 * 
	 * @param data
	 * @param l
	 * @param u
	 */
	public static void qsort2(int[] data, int l, int u) {
		if (l >= u) {
			return;
		}

		// System.out.println(Arrays.toString(data));

		int t = data[l];
		int m = l;
		for (int i = l + 1; i <= u; i++) {
			if (data[i] < t) {
				// 交换m+1和i位置的元素
				m++;
				swap(data, m, i);
			}
		}

		swap(data, l, m);

		qsort2(data, l, m - 1);
		qsort2(data, m + 1, u);
		// System.out.println(Arrays.toString(data));

	}

	/**
	 * 插入排序
	 * 
	 * @param data
	 * @param l
	 * @param u
	 */
	public static void isort(int[] data) {
		if (data.length <= 1) {
			return;
		}

		int i, j;
		for (i = 1; i < data.length; i++) {
			int t = data[i];
			for (j = i; j > 0 && t < data[j - 1]; j--) {
				data[j] = data[j - 1];
			}
			data[j] = t;
		}
	}

	/**
	 * 交换数组两个位置的元素
	 * 
	 * @param data
	 * @param p1
	 * @param p2
	 */
	private static void swap(int[] data, int p1, int p2) {

		int temp = data[p1];
		data[p1] = data[p2];
		data[p2] = temp;
	}
}
